package com.leetcode.algs4.sort;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/6/14 17:15
 */
public class QuickSort2 {

    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70, 0};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int low, int high) {
        if (low >= high) return;
        int p = partition(arr, low, high);
        // 对左半部分和右半部分切分，不包括切分点
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int l = low, h = high + 1; // 取low可以不包括切分点
        int v = arr[l]; // 切分点
        while (true) {
            // 找到较大值和较小值的位置
            // 走到头了
            // 不断交换满足条件的值
            while (v > arr[++l] && l != high) ;
            while (v < arr[--h] && h != low) ;
            // 相遇则退出
            if (l >= h) break;
            swap(arr, l, h);
        }
        // 此时指针相遇，交换低位，因为是选择低位作为切分点
        swap(arr, low, h);
        return h;
    }




    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
